﻿#include <iostream>
#include <cstring>
using namespace std;

typedef struct element
{
	double coef;
	int expn;
	element *next;
}elem, *List;

List p1 = NULL;
List p2 = NULL;

bool handleCoef(double &coe)
{
	char input[10];
	cin >> input;
	if (input[0] == '#')
		return false;
	else
		coe = atof(input);
	return true;
}

int getSize(List p)
{
	List pt = p;
	if (pt == NULL)
		return 0;
	int cnt = 0;
	while (pt != NULL)
	{
		++cnt;
		pt = pt->next;
	}
	return cnt;
}

void checkPolyn(List &p)
{
	List cur = p;
	List bfr = cur;
	while (cur != NULL)
	{
		cur = cur->next;
		while (cur != NULL && bfr->expn == cur->expn)
		{
			bfr->coef += cur->coef;
			bfr->next = cur->next; //删除当前结点
			cur = cur->next;
		}
		bfr = bfr->next;
	}
}

void sortPolyn(List &p)
{
	List t1 = NULL;
	List t2 = NULL;
	int exp;
	double coe;
	for (t1 = p; t1 != NULL; t1 = t1->next)
	{
		for (t2 = t1; t2 != NULL; t2 = t2->next)
		{
			if (t2->expn < t1->expn)
			{
				exp = t1->expn;
				t1->expn = t2->expn;
				t2->expn = exp;
				coe = t1->coef;
				t1->coef = t2->coef;
				t2->coef = coe;
			}
		}
	}
}

void CreatPolyn(List &p)
{
	if (p != NULL)
	{
		cout << "多项式已创建！" << endl;
		return;
	}
	List head = p;
	List temp1 = NULL;
	List temp2 = NULL;
	cout << "依次输入系数和指数(系数输入#以结束)：\n";
	double coe;
	int exp;
	while (1)
	{
		temp1 = new elem;
		cout << "系数：";
		if (handleCoef(coe) == false)
		{
			if (temp2 != NULL)
			{
				cout << "创建成功！" << endl;
				temp2->next = NULL;
			}
			delete temp1;
			p = head;
			sortPolyn(p);
			checkPolyn(p);
			return;
		}
		cout << "指数：";
		cin >> exp;
		if (coe == 0)  continue;
		temp1->coef = coe;
		temp1->expn = exp;
		if (head == NULL)
			head = temp1;
		else
			temp2->next = temp1;
		temp2 = temp1;
		cout << "\n\n";
	}
}


void PrintList(List p)
{
	if (p == NULL)
	{
		cout << "尚未创建！" << endl;
		return;
	}
	List pt = p;
	int sign = 0;
	while (pt != NULL)
	{
		if (pt->coef != 0)
		{
			if (sign == 0)
				cout << pt->coef;
			else
				pt->coef < 0 ? cout << " - " << abs(pt->coef) : cout << " + " << abs(pt->coef);
			sign = 1;
			if (pt->expn != 0)
				pt->expn == 1 ? cout << "x" : cout << "x^" << pt->expn;
		}
		pt = pt->next;
	}
	if (sign == 0)
		cout << "\n0\n";
	cout << endl;
}

void DestroyPoly(List &p)
{
	List head = p;
	if (head != NULL)
	{
		List temp = head;
		while (temp != NULL)
		{
			head = head->next;
			delete temp;
			temp = head;
		}
	}
	p = NULL;
	cout << "已清除多项式！" << endl;
}


void addPolyn(int neg)
{
	List res = NULL;
	List head = res;
	if (p1 == NULL || p2 == NULL)
	{
		cout << "请输入更多的多项式！" << endl;
		return;
	}
	List tp1 = new elem;
	List tp2 = NULL;
	List temp = p1;
	while (temp != NULL)
	{
		tp1->coef = temp->coef;
		tp1->expn = temp->expn;
		if (head == NULL)
			head = tp1;
		else
			tp2->next = tp1;
		tp2 = tp1;
		temp = temp->next;
		tp1 = new elem;
	}
	temp = p2;
	while (temp != NULL)
	{
		tp1->coef = neg*temp->coef;
		tp1->expn = temp->expn;
		tp2->next = tp1;
		tp2 = tp1;
		temp = temp->next;
		tp1 = new elem;
	}
	tp2->next = NULL;
	res = head;
	sortPolyn(res);
	checkPolyn(res);
	PrintList(res);
	delete tp1;
}

void multiPolyn()
{
	if (p1 == NULL || p2 == NULL)
	{
		cout << "请输入更多的多项式！" << endl;
		return;
	}
	List res = NULL;
	List head = res;
	List tp1 = new elem;
	List tp2 = NULL;
	for (List t1 = p1; t1 != NULL; t1 = t1->next)
	{
		for (List t2 = p2; t2 != NULL; t2 = t2->next)
		{
			tp1->coef = t1->coef*t2->coef;
			tp1->expn = t1->expn + t2->expn;
			if (head == NULL)
				head = tp1;
			else
				tp2->next = tp1;
			tp2 = tp1;
			tp1 = new elem;
		}
	}
	tp2->next = NULL;
	res = head;
	sortPolyn(res);
	checkPolyn(res);
	PrintList(res);
	delete tp1;
}

int main()
{
	int i;
	while (1)
	{
		cout << "1.输入  2.打印  3.项数  4.相加  5.相减  6.相乘  7.清除  8.退出" << endl;
		cout << "输入菜单项：" << endl;
		cin >> i;
		switch (i)
		{
		case 1: {
			cout << "1--输入第一个多项式  2--输入第二个多项式" << endl;
			int ch;
			cin >> ch;
			if (ch == 1)
				CreatPolyn(p1);
			else if (ch == 2)
				CreatPolyn(p2);
			break;
		}
		case 2: {
			cout << "第一个多项式：" << endl;
			PrintList(p1);
			cout << "第二个多项式：" << endl;
			PrintList(p2);
			break;
		}
		case 3: {
			cout << "第一个多项式项数为" << getSize(p1) << endl;
			cout << "第二个多项式项数为" << getSize(p2) << endl;
			break;
		}
		case 4: {
			cout << "相加\n\n";
			addPolyn(1);
			break;
		}
		case 5: {
			cout << "相减\n\n";
			addPolyn(-1);
			break;
		}
		case 6: {
			cout << "相乘\n\n";
			multiPolyn();
			break;
		}
		case 7: {
			cout << "1--清除第一个多项式  2--清除第二个多项式" << endl;
			int ch;
			cin >> ch;
			if (ch == 1)
				DestroyPoly(p1);
			else if (ch == 2)
				DestroyPoly(p2);
			break;
		}
		case 8: {
			cout << "退出" << endl;
			return 0;
		}

		default:
			break;
		}
		cout << endl;
		system("pause");
		system("cls");
	}
	return 0;
}
